package demo.ybt;

public class P1258_2 {
    public static void main(String[] args) {
        P1258_2 p1258_2= new P1258_2();
        int res = p1258_2.res(new int[][]{{13, 0, 0, 0, 0}, {11, 8, 0, 0, 0}, {12, 7, 26, 0, 0},
                {6, 14, 15, 8, 0}, {12, 7, 13, 24, 11}});
        System.out.println(res);
    }
    public int res(int[][] t){

        int h= t.length;
        int w=t[0].length;

        int[][] dp = new int[h][w];
        for(int j=0;j<w;j++){
            dp[0][j]=t[0][j];
        }

        int max=t[0][0];
        for(int i=1;i<h;i++){
            for(int j=0;j<w;j++){
                if(j-1>=0){
                    dp[i][j]= Math.max(t[i][j]+dp[i-1][j-1],t[i][j]+ dp[i-1][j]);
                }else{
                    dp[i][j]=t[i][j]+ dp[i-1][j];
                }
                max= Math.max(max,dp[i][j]);
            }
        }

        return max;

    }
}
